An evolutionary algorithm (EA) is a subset of evolutionary computation, a generic population-based metaheuristic optimization algorithm. EAs use one or more operators inspired by biological evolution, which include reproduction, mutation, recombination, and selection. Candidate solutions to an optimization problem play the role of individuals in a population. A fitness function determines an environment within which the candidate solutions “live”. Evolution of the population then takes place after repeated application of the operators.
Generally, an initial population of randomly generated candidate solutions forms a first generation. The fitness function is applied to the candidate solutions and any offspring. In selection, parents for the next generation are chosen with a bias towards higher fitness. The parents reproduce by copying with recombination and/or mutation. Recombination acts on the two selected parents (candidates) and results in one or two children (new candidates). Mutation acts on one candidate and results in a new candidate. These operators create the offspring (a set of new candidates). These new candidates compete with old candidates for their place in the next generation. This process may be repeated until a candidate with sufficient quality (a solution) is found or a predefined computational limit is reached.
EAs are of many different types and can be used to find solutions to problems in diverse fields. The fields may include engineering, robotics, physics, chemistry, biology, genetics, operations research, economics, sales, marketing, and so on.
A genetic algorithm (GA) is a type of EA. GAs provide solutions to complex optimization problems. GAs are stochastic search methods based on principles of natural genetic systems. In an example of a GA, an initial population is chosen, and fitness of each individual in the population is evaluated. Then the following steps are repeated until a stopping criterion is satisfied: Selecting best ranking individuals to reproduce; breeding a new generation through crossover and mutation (called genetic operations) and giving birth to offspring (strings); evaluating fitness of each individual offspring; and retaining best ranked offspring obtained so far. The stopping criterion determines when to stop (i.e., terminate) the GA.
GAs perform a multidimensional search in providing an optimal solution for an evaluation function (i.e., a fitness function) of an optimization problem. Unlike conventional search methods, GAs deal simultaneously with multiple solutions and use only fitness function values. Population members are represented by strings corresponding to chromosomes. Search begins with a population of randomly selected strings. From these strings, a next generation is created using genetic operators. At each iteration, individual strings are evaluated with respect to a performance criterion and are assigned a fitness value. Strings are selected based on these fitness values in order to produce the offspring for the next generation. Thus, successive populations of feasible solutions are generated in stochastic manner following laws of natural selection.
GAs have been theoretically and empirically found to provide global near-optimal solutions for complex optimization problems in various fields. For example, the fields include, but are not limited to, operations research, very large scale integration (VLSI) circuit design, pattern recognition, image processing, machine learning, and so on.